package LeetCode;

import java.util.HashMap;
import java.util.Map;

public class LC_494_TargetSum {

    public static void main(String[] args) {

    }

    class Solution {
        public int findTargetSumWays(int[] nums, int S) {
            int[] arr = new int[1];
            helper(nums, S, arr, 0, 0);
            return arr[0];
        }

        void helper(int[] nums, int S, int[] arr, int sum, int start) {
            if (start == nums.length) {
                if (sum == S) arr[0]++;
                return;
            }
            helper(nums, S, arr, sum - nums[start], start + 1);
            helper(nums, S, arr, sum + nums[start], start + 1);
        }

    }

    static class Solution_2 {

        public int findTargetSumWays(int[] nums, int S) {
            if (nums == null || nums.length == 0) return 0;
            return helper(nums, S, 0, 0, 0);
        }

        int helper(int[] nums, int S, int sum, int index, int count) {
            if (index == nums.length) {
                if (sum == S) count++;
                return count;
            }
            return helper(nums, S, sum + nums[index],
                    index + 1, count) + helper(nums, S, sum - nums[index], index + 1, count);
        }

    }

    static class Solution_3 {
        public int findTargetSumWays(int[] nums, int S) {
            if (nums == null || nums.length == 0) return 0;
            return helper(nums, 0, 0, S, new HashMap<>());
        }

        private int helper(int[] nums, int index, int sum, int S, Map<String, Integer> map) {
            String encodeString = index + "->" + sum;
            if (map.containsKey(encodeString)) return map.get(encodeString);
            if (index == nums.length) {
                if (sum == S)
                    return 1;
                else
                    return 0;
            }
            int curNum = nums[index];
            int add = helper(nums, index + 1, sum - curNum, S, map);
            int minus = helper(nums, index + 1, sum + curNum, S, map);
            map.put(encodeString, add + minus);
            return add + minus;
        }

    }

    static class Solution_4 {
        public int findTargetSumWays(int[] nums, int S) {
            int sum = 0;
            for (int num : nums)
                sum += num;
            if (S > sum || (sum + S) % 2 == 1)
                return 0;
            return subsetSum(nums, (sum + S) / 2);
        }

        private int subsetSum(int[] nums, int S) {
            int[] dp = new int[S + 1];
            dp[0] = 1;
            for (int num : nums) {
                for (int j = S; j >= num; j--) {
                    dp[j] += dp[j - num];
                }
            }
            return dp[S];
        }
    }

}